package demo1;
import java.util.*;
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}
public class Solution {
     //1.剑指 Offer 27. 二叉树的镜像
     public TreeNode mirrorTree(TreeNode root) {
          if (root == null) {
               return root;
          }
          swap(root);//交换左右子树
          mirrorTree(root.left);//继续交换左子树
          mirrorTree(root.right);//继续交换右子树
          return root;
     }

     private void swap(TreeNode root) {
          TreeNode tmp = root.left;
          root.left = root.right;
          root.right = tmp;
     }

     //2.剑指 Offer 28. 对称的二叉树(双百)
     public boolean isSymmetric(TreeNode root) {
          if (root == null) {//空树也算对称
               return true;
          }
          return isSymmetricChild(root.left, root.right);
     }

     private boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
          //一个为空一个不为空，不对称
          if (leftTree == null && rightTree != null ||
                  leftTree != null && rightTree == null) {
               return false;
          }
          //都为空，对称
          if (leftTree == null && rightTree == null) {
               return true;
          }
          //值不相等，不对称
          if (leftTree.val != rightTree.val) {
               return false;
          }
          //递归的去看左子树左节点和右子树的右节点 && 右子树的左节点和左子树的右节点 是否相同
          return isSymmetricChild(leftTree.left, rightTree.right) &&
                  isSymmetricChild(leftTree.right, rightTree.left);
     }

     //3.剑指 Offer 32 - II. 从上到下打印二叉树 II(辅助队列)
/*     public List<List<Integer>> levelOrder(TreeNode root) {
          //队列
          List<List<Integer>> ret = new ArrayList<>();
          if (root == null) {
               return ret;
          }
          Queue<TreeNode> queue = new LinkedList<>();
          queue.offer(root);
          while (!queue.isEmpty()) {
               int size = queue.size();//记录当前这队列(这一行)的长度
               List<Integer> row = new ArrayList<>();//当前行
               while (size > 0) {
                    TreeNode node = queue.poll();
                    row.add(node.val);
                    //左右子树不为空就放入队列(下一行)
                    if (node.left != null) {
                         queue.offer(node.left);
                    }
                    if (node.right != null) {
                         queue.offer(node.right);
                    }
                    size--;
               }
               //加入当前行
               ret.add(row);
          }
          return ret;
     }*/

     //4.剑指 Offer 55 - I. 二叉树的深度(DFS)
     public int maxDepth(TreeNode root) {
          if (root == null) {
               return 0;
          }
          int left = maxDepth(root.left);
          int right = maxDepth(root.right);
          return Math.max(left, right) + 1;
     }
     /*}
     //5.剑指 Offer 54. 二叉搜索树的第k大节点(dfs)
     /*List<Integer> list = new ArrayList<>();//
     public int kthLargest(TreeNode root, int k) {
          //中序遍历得到递增序列
          dfs(root);
          return list.get(list.size() - k);
     }
     private void dfs(TreeNode root) {
          if(root == null) {
               return;
          }
          dfs(root.left);
          list.add(root.val);
          dfs(root.right);
     }*/

     //5.剑指 Offer 54. 二叉搜索树的第k大节点(优化)
     public int key;
     public int k;
     public int kthLargest(TreeNode root, int k) {
          //中序遍历得到递增序列，由此倒叙中序遍历就可以得到递减序列
          this.k = k;
          dfs(root);
          return key;
     }
/*     private void dfs(TreeNode root) {
          if(root == null) {
               return;
          }
          dfs(root.right);
          if(k == 0) {
               return;
          }
          if(--k == 0) {
               key = root.val;
               return;
          }
          dfs(root.left);
     }*/

     //6.剑指 Offer 55 - II. 平衡二叉树
     public boolean isBalanced(TreeNode root) {
          if(root == null) {
               return true;
          }
          //求左右子树高度
          int leftHigh = dfs(root.left);
          int rightHigh = dfs(root.right);
          //高度差必须小于1，同时每一刻根节点都需要满足此要求
          return Math.abs(leftHigh - rightHigh) <= 1 &&
                  isBalanced(root.left) && isBalanced((root.right));
     }
     //求树的高度(深度优先搜索)
     private int dfs(TreeNode root) {
          if(root == null) {
               return 0;
          }
          int left = dfs(root.left);
          int right = dfs(root.right);
          return left > right ? left + 1 : right + 1;
     }
     //7.剑指 Offer 32 - I. 从上到下打印二叉树(队列)
/*     public int[] levelOrder(TreeNode root) {
          if(root == null) {
               int[] tmp = {};
               return tmp;
          }
          //二叉树的层序遍历——队列
          Queue<TreeNode> queue = new LinkedList<>();
          List<Integer> list = new ArrayList<>();
          queue.offer(root);
          while(!queue.isEmpty()) {
               TreeNode node = queue.poll();
               if(node.left != null) {
                    queue.offer(node.left);
               }
               if(node.right != null) {
                    queue.offer(node.right);
               }
               list.add(node.val);
          }
          int[] ret = new int[list.size()];
          for(int i = 0; i < list.size(); i++) {
               ret[i] = list.get(i);
          }
          return ret;
     }*/
     //8.剑指 Offer 68 - I. 二叉搜索树的最近公共祖先(BFS)
     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          //用两个链表记录下p,q的路径
          List<TreeNode> pPath = new ArrayList<>();
          List<TreeNode> qPath = new ArrayList<>();
          TreeNode cur = root;
          //寻找p的路径
          while(cur != null) {
               pPath.add(cur);
               if(cur.val > p.val) {
                    cur = cur.left;
               }else if(cur.val < p.val) {
                    cur = cur.right;
               }else {
                    break;
               }
          }
          //寻找q的路径
          cur = root;
          while(cur != null) {
               qPath.add(cur);
               if(cur.val > q.val) {
                    cur = cur.left;
               }else if(cur.val < q.val) {
                    cur = cur.right;
               }else {
                    break;
               }
          }
          //从后向前对比，第一个相等的就是最近公共祖先
          int min = pPath.size() < qPath.size() ? pPath.size() : qPath.size();
          for(int i = min - 1; i >= 0; i--) {
               if(pPath.get(i) == qPath.get(i)) {
                    return pPath.get(i);
               }
          }
          return null;
     }
     //9.剑指 Offer 32 - III. 从上到下打印二叉树 III(双端队列)
     public List<List<Integer>> levelOrder(TreeNode root) {
          List<List<Integer>> ret = new ArrayList<>();
          if(root == null) {
               return ret;
          }
          //双端队列
          Deque<TreeNode> deque = new LinkedList<>();
          deque.offerFirst(root);
          boolean flag = true;//true,从左向右打印，为false，从右向左
          while(!deque.isEmpty()) {
               //装一行的元素
               Deque<Integer> row = new LinkedList<>();
               int size = deque.size();//一行的大小
               //弹出这一行，放入顺序表(按什么顺序弹？用一个flag)
               for(int i = size; i > 0; i--) {
                    TreeNode node = deque.poll();
                    if(!flag) {
                         row.offerFirst(node.val);
                    }else {
                         row.offerLast(node.val);
                    }
                    //将其子树放入队列
                    if(node.left != null) {
                         deque.offer(node.left);
                    }
                    if(node.right != null) {
                         deque.offer(node.right);
                    }
               }
               flag = !flag;
               //放入ret中
               ret.add(new ArrayList<>(row));
          }
          return ret;
     }
     //10.二叉树的最小深度
     public int minDepth(TreeNode root) {
          if(root == null) {
               return 0;
          }
          //若左右子树都为空，直接返回一
          if(root.left == null && root.right == null) {
               return 1;
          }
          //递归左右子树
          int left = minDepth(root.left);
          int right = minDepth(root.right);
          if(root.left == null || root.right == null) {
               return left + right + 1;
          }
          //左右子树都不为空，返回最小的那颗
          return Math.min(left, right) + 1;
     }
}
